package leetcode.violence;

public class postage {
        /*
    连续邮资问题:
    假设国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。
    连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，
    在一张张信封上可以贴出从邮资1开始，增量为1的最大连续邮资区间。

    举例分析:
    当n=2,m=3时，如果面值分别为1和4，则可以获得的邮资范围为1~6 加上 8 , 9 , 12。但是8,9,12已经是不连续的和了。
    如果面值为1,3，则可以获得1~7之间的每个邮资值，并且7就是可以得到的连续的邮资最大值。


    前解，递归调用 ， 回溯

    输入:
    2
    2 3
    5 4

    输出:
    7
    1 3

    70
    1 3 11 15 32
    */


    static final int NUM = 10;
    static final int LEN = 10000;
    static int[] x = new int[NUM];
    static int cnt = 0;//当前邮票种类
    static int[] r = new int[NUM];//用于面值结果
    static int max = 0;//最大值

    static int[][] C = new int[NUM][LEN]; //记录搜索结点状态

    /*
     * 计算当前邮票面值的最大连续邮资区间
     * */
    public static int findMax(int knd, int lim) {
        int j = 1;
        while (C[cnt - 1][j] != 0) {
            if (j < x[cnt] || C[cnt - 1][j] <= C[cnt][j - x[cnt]] + 1)
                C[cnt][j] = C[cnt - 1][j];
            else
                C[cnt][j] = C[cnt][j - x[cnt]] + 1;
            j++;
        }

        while (true) {
            int tmp = Integer.MAX_VALUE;
            for (int i = 1; i <= cnt; i++) {
                if (tmp > C[cnt][j - x[i]] + 1)
                    tmp = C[cnt][j - x[i]] + 1;
            }
            if (tmp == Integer.MAX_VALUE || tmp > lim)
                break;
            else
                C[cnt][j] = tmp;
            j++;
        }
        C[cnt][j] = 0;
        return j - 1;
    }

    public static void dfs(int type, int limit) {
        if (cnt == type) {
            if (x[cnt] * limit < max)
                return;
            int tmp = findMax(type, limit);
            if (tmp > max) {
                max = tmp;//若比记录的最大连续邮资区间上限大，则更新
                for (int i = 1; i <= type; i++) //记录新的邮票面值组合
                    r[i] = x[i];
            }
        } else {
            int tmp = findMax(type, limit);
            for (int i = tmp + 1; i >= x[cnt] + 1; i--) {
                x[++cnt] = i;//将可能面值加入当前面值组合中
                dfs(type, limit);
                cnt--;
            }
        }
    }


    public static void main(String args[]) {
        int limit = 4; //允许贴4张邮票
        int type = 5; //面值有5种

        //从面值1开始，必须得有1，否则很多数值都不能构成。
        x[1] = 1;
        //因为面值1是第一种，所以cnt=1
        cnt = 1;//当前邮票种类
        dfs(type, limit);
        System.out.println("MAX = " + max);
        for (int i = 1; i <= type; i++) {
            System.out.println(r[i] + " ");
        }


    }

}
